package 栈;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.HashMap;
import java.util.Map;

public class NC52括号序列 {

    /**
     * 给出一个仅包含字符'(',')','{','}','['和']',的字符串，判断给出的字符串是否是合法的括号序列
     * 括号必须以正确的顺序关闭，"()"和"()[]{}"都是合法的括号序列，但"(]"和"([)]"不合法。
     */

    public boolean isValid (String s) {

        Map<Character,Character> map=new HashMap<>();
        map.put(')','(');
        map.put('}','{');
        map.put(']','[');
        char[] arr=s.toCharArray();
        Deque<Character> stack=new ArrayDeque<>();
        int index=0;

        while (index< arr.length){

            if(arr[index]=='('||arr[index]=='{'||arr[index]=='['){
                //起始括号
                stack.addLast(arr[index]);
            }else{
                //闭括号
                if(map.get(arr[index])!=stack.pollLast()){
                    return false;
                }
            }
            index++;
        }

        return stack.isEmpty();
    }

}
